package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.base.ListNode;
import com.xsherl.leetcode.base.TreeNode;
import com.xsherl.leetcode.utils.PrintUtils;

public class ConvertSortedListToBinarySearchTree {

    ListNode head = null;
    /**
     * 链表等于中序遍历平衡二叉树的结果
     * 所以可以通过中序遍历来构建平衡二叉树
     */
    public TreeNode sortedListToBST(ListNode head) {
        int len = getLen(head);
        this.head = head;
        return buildTreeInorder(0, len - 1);
    }

    public int getLen(ListNode head){
        int len = 0;
        while (head != null){
            len++;
            head = head.next;
        }
        return len;
    }

    public TreeNode buildTreeInorder(int left, int right){
        if (left > right){
            return null;
        }
        int mid = (left + right) / 2;
        TreeNode root = new TreeNode();
        root.left = buildTreeInorder(left, mid - 1);
        root.val = head.val;
        head = head.next;
        root.right = buildTreeInorder(mid + 1, right);
        return root;
    }

    /**
     * 通过快慢指针获取链表的中位数
     */
    public TreeNode sortedListToBST1(ListNode head) {
        return buildTree(head, null);
    }

    public TreeNode buildTree(ListNode begin, ListNode end){
        if (begin == end){
            return null;
        }
        ListNode mid = getMid(begin, end);
        TreeNode root = new TreeNode(mid.val);
        root.left = buildTree(begin, mid);
        root.right = buildTree(mid.next, end);
        return root;
    }

    public ListNode getMid(ListNode begin, ListNode end){
        ListNode fast = begin, slow = begin;
        while (fast != end && fast.next != end){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    public static void main(String[] args) {
        ListNode head = ListNode.build(-10, -3, -2, -1, 0, 5, 9);
        TreeNode node = new ConvertSortedListToBinarySearchTree().sortedListToBST(head);
        PrintUtils.println(node);
    }
}
